package stu.day25_day32.day31;

public class hw3 {



    char[][] ch = new char[9][9];
    public void solveSudoku(char[][] board) {

       backtrack(0,0,board);
       System.arraycopy(ch, 0, board, 0, 9);

    }



    public void backtrack(int i,int j,char[][] board){
        if (i == 9) {
            for (int x = 0; x < 9; x++) {
                ch[x] = board[x].clone();
            }
            return;
        }

        if(board[i][j]=='.'){
            for(char ch='1';ch<='9';ch++){
                if(isValid(board,i,j,ch)){
                    board[i][j] = ch;
                    if (j==8) {
                        backtrack(i + 1, 0, board);
                    } else {
                        backtrack(i, j + 1, board);
                    }
                    board[i][j] = '.';
                }
            }

        }else {
            if (j==8) {
                backtrack(i + 1, 0, board);
            } else {
                backtrack(i, j + 1, board);
            }
        }
    }


    // 判断当前位置是否遵循数独的 3 个规则
    private static boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // 1、数字 1-9 在每一行只能出现一次
            // 判断当前这一行是否已经有 c 这个数字存在
            if (board[row][i] == c)
                return false;
            // 2、数字 1-9 在每一列只能出现一次
            // 判断当前这一列是否已经有 c 这个数字存在
            if (board[i][col] == c)
                return false;
            // 3、数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
            // 判断当前这个九宫格是否已经有 c 这个数字存在
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
                return false;
        }
        // 如果遵循了这 3 个规则
        // 说明可以填充 c 这个数字
        return true;
    }


}
